sciencefandomcom_el-20200214-history
Μαθηματική Λογική
Μαθηματική Λογική Mathematical logic thumb|300px| [[Μαθηματικά Γεωμετρία Άλγεβρα Μαθηματική Λογική Μαθηματική Ανάλυση Διακριτά Μαθηματικά Τοπολογία Γραμμική Άλγεβρα Στατιστική Οικονομικά Μαθηματικά ]] - Ένας Επιστημονικός Κλάδος των Μαθηματιών. Ετυμολογία Η ονομασία "Μαθηματική" σχετίζεται ετυμολογικά με την λέξη "Μαθηματικά". Εισαγωγή Η Μαθηματική Λογική είναι μια βασική περιοχή των Μαθηματικών που εξελίχθηκε από τη Συμβολική Λογική. Πεδία της Μαθηματικής Λογικής είναι η Θεωρία Προτύπων (model theory), η Θεωρία Αποδείξεων (proof theory), η Θεωρία Συνόλων και η Θεωρία Αναδρομής (recursion theory). Η έρευνα στη Μαθηματική Λογική συμβάλλει στη μελέτη των "θεμελίων των Μαθηματικών", αλλά η Μαθηματική Λογική περιέχει ακόμα πεδία των αμιγών Μαθηματικών, που δεν σχετίζονται με θεμελιακές ερωτήσεις. Η Μαθηματική Λογική σχετίζεται στενά με την μελέτη της (πολύ παλαιότερης) Τυπικής Λογικής στη Φιλοσοφία, που ξεκίνησε με τον Αριστοτέλη. Δίνει έναν ευκολότερο και πληρέστερο τρόπο για τον έλεγχο της ορθότητας ισχυρισμών από ότι οι κλασσικές Αριστοτελικές μορφές. Η Μαθηματική Λογική σχετίζεται επίσης στενά με τα Μεταμαθηματικά. Ένα ενοποιητικό θέμα στη μαθηματική λογική είναι η μελέτη της εκφραστικής ισχύος των τυπικών λογικών και των τυπικών συστημάτων αποδείξεων. Η ισχύς αυτή μετράται με το ποιες μαθηματικές έννοιες μπορούν να ορισθούν και ποιά θεωρήματα μπορούν να αποδειχθούν σε αυτά τα τυπικά συστήματα. Ιστορία Μαθηματική Λογική ονομάστηκε από τον Τζουζέπε Peano αυτό που αργότερα ονομάσθηκε συμβολική Λογική. Στην κλασσική της έκδοση, οι βασικές αρχές θυμίζουν τη Λογική του Αριστοτέλη, γραμμένες όμως με συμβολικό τρόπο αντί για φυσική γλώσσα. Ορισμένοι από τους πιο φιλοσοφικούς μαθηματικούς έκαναν προσπάθειες να χειριστούν τις πράξεις της Τυπικής Λογικής με συμβολικό ή αλγεβρικό τρόπο, όπως ο Γκόντφριντ Βίλχελμ Leibnitz και ο Γιόχαν Χάινριχ Lambert, αλλά οι προσπάθειές τους έμειναν άγνωστες και απομονωμένες. Ήταν ο Τζορτζ Boole και ο Αύγουστος De Morgan, στο μέσο του 19ου αιώνα που παρουσίασαν ένα συστηματικό τρόπο μελέτης της λογικής. Το παραδοσιακό Αριστοτέλειο δόγμα της Λογικής αναμορφώθηκε και συμπληρώθηκε, και από αυτή την εξέλιξη προέκυψε ένα επαρκές εργαλείο για τη μελέτη των θεμελιακών ιδεών των Μαθηματικών. Θα ήταν παραπλανητικό να ισχυρισθεί κανείς ότι οι θεμελιακές διαμάχες που υπήρχαν την περίοδο 199 - 1925 έχουν όλες λυθεί, αλλά η Φιλοσοφία Μαθηματικών έχει διευκρινιστεί σε μεγάλο βαθμό από τη «νέα» Λογική. Η αρχική Ελληνική ανάπτυξη της λογικής έδωσε μεγάλη έμφαση στις μορφές των ισχυρισμών, ενώ η συμπεριφορά της τρέχουσας Μαθηματικής Λογικής μπορεί να συνοψισθεί ως η συνδυαστική μελέτη του περιεχομένου. Αυτό καλύπτει τόσο το συντακτικό όσο και την ερμηνεία, δηλαδή τόσο τη μορφή των εκφράσεων όσο και το νόημά τους. Στην Επιστήμη Υπολογιστών, εντελώς συντακτική μελέτη επιτρέπει σε μια συμβολοσειρά από μια Τυπική Γλώσσα να μετασχηματισθεί από ένα μεταγλωττιστή σε μια σειρά εντολών μηχανής. Η εννοιολογική μελέτη επιτρέπει σε έναν προγραμματιστή να επιλέξει ποιες συμβολοσειρές να χρησιμοποιήσει για να επιτύχει ένα συγκεκριμένο στόχο. Κάποιες σημαντικές δημοσιεύσεις στη Μαθηματική Λογική περιέχουν: *το "Begriffsschrift" του Γκότλομπ Φρέγκε, *τις "Studies in Logic" του Τσαρλς Πέιρς την "Principia Mathematica" του Μπέρτραντ Ράσσελ και του Άλφρεντ Νορθ Γουάιτχεντ και *το "On Formally Undecidable Propositions of Principia Mathematica and Related Systems" του Κουρτ Γκέντελ. Τυπική Λογική Στον πυρήνα της, η μαθηματική λογική χειρίζεται μαθηματικές έννοιες που εκφράζονται χρησιμοποιώντας τυπικά συστήματα λογικής. Το σύστημα της "Λογικής πρώτου βαθμού" (first-order logic) έχει μελετηθεί περισσότερο λόγω της εφαρμογής του στα "θεμέλια των Μαθηματικών" και λόγω των επιθυμητών του ιδιοτήτων. Μελετώνται επίσης εκφραστικότερες κλασσικές λογικές όπως η "Λογική δευτέρου βαθμού" (second-order logic) ή η Απειρική Λογική (infinitary logic), αλλά και μη κλασσικές λογικές όπως, η Ενορατική Λογική (intuitionistic logic). Πεδία της Μαθηματικής Λογικής Το βιβλίο "Handbook of Mathematical Logic" (1977) διαχωρίζει τη Μαθηματική Λογική σε τέσσερα μέρη: *'Θεωρία Συνόλων' είναι η μελέτη των συνόλων, τα οποία είναι αφηρημένες συλλογές από αντικείμενα. Οι βασικές έννοιες της θεωρίας συνόλων όπως το υποσύνολο και το σχετικό συμπλήρωμα λέγονται συχνά αφελής θεωρία συνόλων. Σύγχρονη έρευνα γίνεται στην περιοχή της αξιωματική αξιωματικής θεωρίας συνόλων, που χρησιμοποιεί λογικές μεθόδους για να μελετήσει ποιες προτάσεις είναι αποδείξιμες σε διάφορες τυπικές θεωρίες όπως η Ζερμέλο-Φράνκελ Θεωρία Συνόλων (ZFC) ή τα "νέα θεμέλια μαθηματικών". *'Θεωρία Αποδείξεων' είναι η μελέτη τυπικών αποδείξεων σε διάφορα συστήματα λογικής αναγωγής. Οι αποδείξεις αυτές αναπαριστώνται σαν τυπικές μαθηματικές οντότητες, διευκολύνοντας την ανάλυσή τους με μαθηματικές τεχνικές. Ο Φρέγκε εργάστηκε πάνω στις μαθηματικές αποδείξεις και τυποποίησε την έννοια της απόδειξης. *'Θεωρία Προτύπων' είναι η μελέτη των μοντέλων από διάφορες τυπικές θεωρίες. Το σύνολο όλων τον μοντέλων μιας δεδομένης θεωρίας λέγεται Στοιχειώδης Κλάση. Η κλασσική θεωρία μοντέλων επιχειρεί να ανακαλύψει τις ιδιότητες των μοντέλων σε κάποια στοιχειώδη κλάση, ή να ανακαλύψει εάν κάποιες κλάσεις από δομές αποτελούν στοιχειώδεις κλάσεις. Η μέθοδος απάλειψης ποσοτικών τελεστών (ποσοδεικτών) χρησιμοποιείται για να δείξει ότι μοντέλα κάποιας θεωρίας δεν μπορεί να είναι υπερβολικά πολύπλοκες. *'Θεωρία Αναδρομής', που λέγεται και θεωρία υπολογισιμότητας, μελετά τις ιδιότητες των υπολογίσιμων συναρτήσεων, και τους βαθμούς Turing, που διαιρούν τις μη-υπολογίσιμες συναρτήσεις σε σύνολα που έχουν το ίδιο επίπεδο μη-υπολογισιμότητας. Η Θεωρία Αναδρομής επίσης περιέχει τη μελέτη της γενικής υπολογισιμότητας και ορισιμότητας. Τα σύνορα μεταξύ των πεδίων αυτών, και ακόμα μεταξύ της Μαθηματικής Λογικής και άλλων πεδίων των Μαθηματικών δεν είναι πάντα καθαρά. Για παράδειγμα, το θεώρημα μη-πληρότητας του Γκέντελ όχι μόνο αποτελεί σταθμό στη Θεωρία Αναδρομής και τη Θεωρία Αποδείξεων, αλλά και έχει οδηγήσει στο θεώρημα Loeb, το οποίο είναι σημαντικό στην Τροπική Λογική. Το μαθηματικό πεδίο της θεωρίας κατηγοριών χρησιμοποιεί πολλές τυπικές αξιωματικές μεθόδους που θυμίζουν αυτές που χρησιμοποιούνται στη Μαθηματική Λογική, αλλά η Θεωρία Κατηγοριών δεν θεωρείται συνήθως υποπεδίο της Μαθηματικής Λογικής. Σχέση με την επιστήμη υπολογιστών Υπάρχει μεγάλη σχέση μεταξύ της μαθηματικής λογικής και της επιστήμης υπολογιστών. Αρχικοί πρωτοπόροι της επιστήμης υπολογιστών, όπως ο Alan Turing, ήταν επίσης μαθηματικοί και λογικοί. Η μελέτη της θεωρίας υπολογισιμότητας στην επιστήμη υπολογιστών σχετίζεται στενά με τη μελέτη της υπολογισιμότητας στη μαθηματική λογική. Διαφέρουν όμως ως προς την έμφαση. Οι επιστήμονες υπολογιστών συχνά εστιάζουν σε πραγματικές γλώσσες προγραμματισμού και την Εφικτή Υπολογισιμότητα (feasible computability), ενώ οι ερευνητές στη μαθηματική λογική συχνά εστιάζουν στην υπολογισιμότητα ως θεωρητική έννοια, και στη μη-υπολογισιμότητα. Η μελέτη της σημασιολογίας (semantics) γλωσσών προγραμματισμού σχετίζεται με την Τροπική Λογική (modal logic), όπως και την Επαλήθευση Προγράμματος (program verification), συγκεκριμένα, τον έλεγχο μοντέλων (model checking). Ο ισομορφισμός Κάρρυ-Χάουαρντ μεταξύ αποδείξεων και προγραμμάτων σχετίζεται με τη Θεωρία Αποδείξεων. Η Ενορατική Λογική και η Γραμμική Λογική είναι σημαντικές σε αυτό. Λογισμοί όπως ο Λογισμός Λάμδα και η Συνδυαστική Λογική (combinatory logic) μελετώνται τελευταία ως ιδεατές γλώσσες προγραμματισμού. Η επιστήμη υπολογιστών συμβάλλει ακόμα στα μαθηματικά με την ανάπτυξη τεχνικών για τον αυτόματο έλεγχο ή και εύρεση αποδείξεων, όπως η Αυτόματη Απόδειξη Θεωρημάτων (automated theorem proving) και ο Λογικός Προγραμματισμός. Σημαντικά αποτελέσματα * Το θεώρημα Λόβενχαιμ-Σκόλεμ (1919) έδειξε ότι αν ένα σύνολο από προτάσεις σε μια μετρήσιμη γλώσσα πρώτου βαθμού έχει ένα άπειρο μοντέλο, τότε έχει τουλάχιστον ένα μοντέλο από κάθε άπειρη πληθικότητα (infinite cardinality). * Το Θεώρημα Πληρότητας του Goedel (1929) εδραίωσε την ισοδυναμία μεταξύ συντακτικών και εννοιολογικών ορισμών με λογική σημασία στη λογική πρώτου βαθμού. * Το θεώρημα μη-πληρότητας του Goedel (1931) έδειξε ότι κανένα αρκετά ισχυρό τυπικό σύστημα δεν μπορεί να αποδείξει την συνέπεια του εαυτού του. * Η μη ύπαρξη αλγοριθμικής λύσης του προβλήματος απόφασης (Entscheidungsproblem) του Ντάβιντ Hilbert, που δείχθηκε ανεξάρτητα από τον Alan Turing και τον Αλόνζο Τσερτς το 1936, έδειξε ότι δεν υπάρχει πρόγραμμα υπολογιστή που μπορεί να αποφασίσει σωστά αν κάποια αυθαίρετη μαθηματική πρόταση είναι αληθής. * Η Λογική Ανεξαρτησία της υπόθεσης του συνεχούς (continuum hypothesis) της Ζερμέλο-Φράνκελ θεωρίας συνόλων (ZFC) έδειξε ότι μια στοιχειώδεις απόδειξη ή ανταπόδειξη της υπόθεσης αυτής είναι αδύνατη. :Το γεγονός ότι η υπόθεση του συνεχούς είναι συνεπής με τη ZFC (αν η ZFC είναι συνεπής από μόνη της) αποδείχθηκε από τον Κουρτ Goedel το 1940. :Το γεγονός ότι η άρνηση της υπόθεσης του συνεχούς είναι συνεπής με τη ZFC (αν η ZFC είναι συνεπής) αποδείχθηκε από τον Πωλ Κοέν το 1963. * Η μη ύπαρξη αλγοριθμικής λύσης για το "δέκατο πρόβλημα Hilbert", που δείχθηκε από τον Γιούρι Ματιγιάσεβιτς το 1970, έδειξε ότι δεν είναι δυνατό για οποιοδήποτε πρόγραμμα υπολογιστή να αποφασίσει σωστά αν πολυώνυμα πολλών μεταβλητών με ακέραιους συντελεστές έχουν ακέραιες λύσεις. Κλάδοι Λογικής *Απειρική Λογική *Ασαφής Λογική *Γραμμική Λογική *Ενορατική Λογική *Κατηγορηματική Λογική *Κλασσική Λογική *Μαθηματική Λογική *Προτασιακή Λογική *Συμβολική Λογική *Συνδυαστική Λογική *Τροπική Λογική *Τυπική Λογική Υποσημειώσεις Εσωτερική Αρθρογραφία *Μαθηματικά *Λογική * Μαθηματική Θεωρία Βιβλιογραφία * Andrews, Peter B., 2002. An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof, 2nd ed. Kluwer Academic Publishers. * Barwise, Jon, ed. (1977) Handbook of Mathematical Logic, Amsterdam: North-Holland. ISBN 0-444-86388-5 * George Boolos, John Burgess, and Richard Jeffrey (2002) Computability and Logic, 4th ed. Cambridge University Press. ISBN 0-521-00758-5. * Enderton, Herbert (2002) A mathematical introduction to logic, 2nd ed. Academic Press. * Hamilton, A. G. (1988) Logic for Mathematicians Cambridge University Press. * Wilfrid Hodges, 1997. A Shorter Model Theory. Cambridge University Press. * Mendelson, Elliott (1997) Introduction to Mathematical Logic, 4th ed. Chapman & Hall. ISBN 0412808307 * A. S. Troelstra & H. Schwichtenberg (2000) Basic Proof Theory, 2nd. ed. (Cambridge Tracts in Theoretical Computer Science). Cambridge University Press. ISBN 0-521-77911-1. * John L. Bell & Alan B. Slomson (1969) Models and Ultraproducts: An Introduction, North-Holland (re-printed in 2006 by Dover publications). ISBN 0-486-44979-3. Ιστογραφία *Ομώνυμο άρθρο στην Βικιπαίδεια *Ομώνυμο άρθρο στην Livepedia * Mathematical Logic around the world * Polyvalued logic * forall x: an introduction to formal logic, by P.D. Magnus, is a free textbook. * Detlovs, Vilnis, and Podnieks, Karlis (University of Latvia) Introduction to Mathematical Logic. A hyper-textbook. *Stanford Encyclopedia of Philosophy: Classical Logic -- by Stewart Shapiro. *Stanford Encyclopedia of Philosophy: First-order Model Theory -- by Wilfred Hodges. Category:Κλάδοι Λογικής Κατηγορία:Επιστημονικοί Κλάδοι Μαθηματικών